package ch5.part8;

import java.util.Arrays;

/**
 * 寻找全排列的下一个数
 * 各步骤之间时间复杂度均为O(n)
 * 合计时间复杂度也为O(n) = n
 *
 * @author liuwanxiang
 * @version 2019/06/17
 */
public class FindNearestNumber {

    private static int TEN = 2;

    private static int[] findNearestNumber(int[] numbers) {
        // 1.从后向前，得到逆序区域的左侧起始点Index
        int index = findTransferPoint(numbers);
        if (index == 0) {
            return null;
        }

        // 2.逆序区域的前一位和逆序区域中的比它答的最小值交换位置
        int[] numbersCopy = Arrays.copyOf(numbers, numbers.length);
        exchangeNumber(numbersCopy, index);

        // 3.对原来的逆序区域进行排序
        reverse(numbersCopy, index);
        return numbersCopy;
    }

    private static int findTransferPoint(int[] numbers) {
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i] > numbers[i - 1]) {
                return i;
            }
        }
        return 0;
    }

    private static void exchangeNumber(int[] numbers, int index) {
        int temp = numbers[index - 1];
        for (int i = numbers.length - 1; i > 0; i--) {
            if (numbers[i] > temp) {
                numbers[index - 1] = numbers[i];
                numbers[i] = temp;
                break;
            }
        }
    }

    private static void reverse(int[] numbers, int index) {
        for (int i = index, j = numbers.length - 1; i < j; i++, j--) {
            int temp = numbers[i];
            numbers[i] = numbers[j];
            numbers[j] = temp;
        }
    }

    public static void main(String[] args) {
        int[] numbers = {1, 2, 3, 4, 5};
        for (int i = 0; i < TEN; i++) {
            numbers = findNearestNumber(numbers);
            printNumbers(numbers);
            if (numbers == null) {
                break;
            }
        }
    }

    private static void printNumbers(int[] numbers) {
        // 空数组的处理逻辑
        if (numbers == null) {
            System.out.print("null\n");
            return;
        }

        // 非空数组的处理逻辑
        for (int number : numbers) {
            System.out.print(number);
        }
        System.out.print("\n");
    }

}
